

//743.网络延迟时间
class Solution {
public:
    int networkDelayTime(vector<vector<int>>& times, int n, int k) {
        //使用堆来实现

        vector<vector<int>> path(n,vector<int>(n,INT_MAX/2));  //记录每个节点之间的距离
        for(auto& tmp : times)
        {
            int x = tmp[0]-1,y = tmp[1]-1,t = tmp[2];
            path[x][y]=t;
        }

        vector<int> dis(n,INT_MAX);                             //记录k到每个位置的最小距离
                                                                //priority_queue记录最短路的位置
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
        pq.push({0,k-1});
        while(pq.size())
        {
            auto [clock,pos]=pq.top();
            pq.pop();
            if(clock>=dis[pos]) continue;               //已经遍历过更优的位置,当前位置不需要扩展了
            dis[pos]=clock;
            for(int k = 0;k < n;k++)                    //向四周进行扩展
            {
                if(clock+path[pos][k]<dis[k])           //当前路径更优,加入到队列中
                    pq.push({clock+path[pos][k],k});
            }
        }        
        int ret=ranges::max(dis);
        return ret>=INT_MAX/2?-1:ret;
    }
};